package com.leetcode.two_pointers.sliding_window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/9/23 14:52
 */
public class FindAnagrams_438 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        while (right < s.length()) {
            char rc = s.charAt(right);
            right++;
            if (need.containsKey(rc)) {
                window.put(rc, window.getOrDefault(rc, 0) + 1);
                if (window.get(rc).compareTo(need.get(rc)) <= 0)
                    valid++;
            }
            if (p.length() == right - left) {
                if (valid == p.length())
                    res.add(left);
                char lc = s.charAt(left);
                if (need.containsKey(lc)) {
                    int num = window.get(lc);
                    if (num <= need.get(lc))
                        valid--;
                    window.put(lc, num - 1);
                }
                left++;
            }
        }
        return res;
    }

    static class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int len1 = s.length(), len2 = p.length();
            Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
            for (int i = 0; i < len2; i++) {
                char c = p.charAt(i);
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            int start = 0, end = len1 - 1, left = 0;
            for (int right = 0; right < len1;) {
                char cr = s.charAt(right);

                if (need.containsKey(cr)) {

                }

            }
            return null;
        }
    }

}
